1. Two Sum

https://leetcode.com/problems/two-sum/description/

Definição

$$\begin{align} L \coloneqq \text{Lista de inteiros}\\ N \coloneqq |N| \space \text{Cardinalidade (tamanho) de L}\\ T \coloneqq \text{Soma esperada}\\ i \coloneqq \text{Índice atual da iteração}\\ \end{align}$$

Intuição

A ideia é iterar $L$ e para cada índice $i$ devemos procurar outro índice $j$ que contenha um complemento $C = L[j]$ então:

$$L[i] + C = T \Rightarrow L[i] + L[j] = T$$

Para encontrar o complemento, usaremos uma tabela de consulta. Não precisamos pré-processar a lista $L$ para construir a tabela de consulta; podemos preenchê-la enquanto iteramos a lista.

Para o elemento atual $L[i]$, procure na tabela uma entrada com o chave $T - L[i]$ que nos forneça um índice $j$ do complemento ou vazio. Se a entrada existir, retorne a resposta $[i, j]$; caso contrário, adicione a entrada $L[i] \Rightarrow i$ à tabela de consulta e repita o processo.

Ilustração

Lista de exemplo: [1, 2, 0, 4, 6]
Soma desejada: 5

1ª Iteração

Na primeira iteração $i$ começa no índice 0 e a tabela de consulta está vazia. O elemento atual é $L[i] = L[0] = 1$, então devemos procurar o complemento $C = T - 1 = 5 - 1 = 4$, mas a tabela de consulta está vazia, então apenas adicionamos o elemento atual à tabela de consulta e incrementamos $i$.

Linha	Chave	Valor

i

1

2

0

4

6

2ª iteração

O elemento atual é $L[i] = L[1] = 2$, então devemos procurar o complemento $C = T - 2 = 5 - 2 = 3$, mas não há nenhuma entrada com a chave $3$ na tabela, então apenas adicionamos o elemento atual à tabela de consulta e incrementamos $i$.

Linha	Chave	Valor
1	1	0

i

1

2

0

4

6

3ª iteração

O elemento atual é $L[i] = L[2] = 0$, então devemos procurar o complemento $C = T - 0 = 5 - 0 = 5$, mas não há nenhuma entrada com a chave $5$ na tabela, então apenas adicionamos o elemento atual à tabela de consulta e incrementamos $i$.

Linha	Chave	Valor
1	1	0
2	2	1

i

1

2

0

4

6

4ª iteração

O elemento atual é $L[i] = L[3] = 4$, então devemos procurar o complemento $C = T - 4 = 5 - 4 = 1$ e ele existe na tabela na linha $1$, que nos dá o índice $0$, então a resposta é $[0, i] = [0, 3]$

Linha	Chave	Valor
1	1	0
2	2	1
3	0	2

i

1

2

0

4

6

Implementação

Clique para revelar a implementação

class Solution:
    def twoSum(self, nums: list[int], target: int) -> list[int]:
        visited_numbers: dict[int, int] = {}

        for i, n in enumerate(nums):
            complement_index = visited_numbers.get(target - n, None)

            if complement_index is not None:
                return [complement_index, i]

            visited_numbers[n] = i

Testes

import pytest
from .solution import Solution


@pytest.mark.parametrize('numbers,target,expected', [
    ([0, 1], 1, [0, 1]),
    ([1, 2, 3], 5, [1, 2]),
])
def test_solution(numbers, target, expected):
    result = Solution().twoSum(numbers, target)
    assert result == expected

Time complexity

No pior caso, o complemento será encontrado no último índice, então precisamos iterar todos os elementos de entrada e preencher/consultar $N - 1$ da tabela. A iteração é $O(n)$ e as inserções/consultas levam $O(1)$ de tempo, supondo que não haja colisões. Portanto, a complexidade de tempo final é $O(n)$.

Space complexity

No pior caso, precisamos preencher a tabela com $N - 1$ entradas, então a complexidade do espaço é $O(N)$.